1. Field of the Invention
The present application generally relates to performance modeling of a complex data processing system when information about the internal structure of the system, the flow of work within the system, and the capacities of resources in the system are not available and, more particularly, to a performance model that captures delay behavior in the actual system, without being too simplistic (e.g., a single server queueing model), or too complicated (e.g., a large queueing network or simulation model).
2. Background Description
Large data processing systems, such as Web serving systems, consist of a multitude of hardware and software components that interact in a complex way. Such components include several tiers of execution units, Web application environments, and databases. The continual management and optimization of system resources in such an environment requires systems performance models that are simple enough to solve, yet representative enough to capture, in a dynamic fashion, the salient performance features of the system. Today's models are either (1) too simplistic or coarse to be useful or (2) too detailed and thus do not lend themselves to dynamic optimization at the time scale (seconds) that is needed for the management of Web serving systems.
Performance modeling and evaluation includes building a queueing model of the computer system as a whole, characterizing the workload to the computer system, and analyzing the queueing model using a workload model to obtain performance measures. Modeling a computer system involves hardware components as well as software components. The hardware components include processing units (CPU), data storage units (RAM and disks), and communication channels. Such hardware components are resources shared by concurrent tasks executing in the system. When a task needs a resource that is not available, the task will wait in a queue until the resource becomes available. The interconnection of resources, along with their multiplicities, their capacities, and corresponding queueing disciplines form the basis for building a queueing model of the system hardware. In addition, there are software resources, such as threads of execution, database locks, and communication connections. Similar to hardware resources, tasks use software resources and queue for their usage if they are not available. Thus, there are queueing models of the system software. An overall system model combines both hardware and software components. The users of system resources, hardware or software, are tasks that get generated due to requests, as in an interactive workload, or due to job submissions, as in batch or long running workload. Different types of workload exhibit different behavior, as far as the amount of resources needed and the usage pattern of such resources are concerned.
The challenge in system performance modeling is to develop a model that is efficient to solve, and yet represents the system behavior and yield accurate performance predictions. At one end of the spectrum, a very simple model is a single server queueing system. In such a model, the single server represents the system as a whole, including hardware and software resources, as a single resource. The queue holds jobs that are waiting to use the system. A job stream constitutes the arrival process to the single server queue. The analysis of such a model is rather straightforward and several performance measures such as response time, waiting time, system utilization, and throughput are easily computed. However, such a simple model assumes that jobs line up to use one resource. Thus, parallelism in resource usage, system delays, contention for multiple resources, and cyclic usage of resources are not captured. The other end of the modeling spectrum is a detailed model that includes all resources, their queueing structures and interconnections. Such a detailed model is typically solved using simulation instead of analysis. The simulation time is usually long, and thus simulation can not be used when dynamically managing the system resources based on performance predictions. A viable approach is to reduce the detailed model to a queueing network model that may be solved numerically under various simplifying assumptions. There are many other analytic techniques such as matrix-geometric techniques and diffusion approximations.
A middle ground is to develop a generic model of the computer system that captures the serialization of tasks as they contend for a resource, the parallelism of tasks as they use multiple resources in parallel, and the inherent system delays due to communication and external processing. The model should provide for the cyclic behavior of tasks and the multiple usages of resources. Furthermore, the model should be easily extended to incorporate multiple types of tasks and work loads. There should be a simple method to estimate the parameters of the model, given high-level system measurements obtained by external monitors, rather than adding instrumentation with detailed level measurement probes to applications.